package roman.algorithm;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BST<T extends Comparable<T>> {
	Node<T> root = null;
	class Node<T>{
		Node<T> left;
		Node<T> right;
		T data;
		public Node(T d){
			data = d;
			left = null;
			right = null;
		}
		public String toString(){
			return data.toString();
		}
	}
	
	public void preorder(Node<T> r){
		if(r==null)
			return;
		System.out.print(r.data);
		preorder(r.left);
		preorder(r.right);
	}
	public void inorder(Node<T> r){
		if(r==null)
			return;
		inorder(r.left);
		System.out.print(r.data);
		inorder(r.right);
	}
	public void postorder(Node<T> r){
		if(r==null)
			return;
		postorder(r.left);
		postorder(r.right);
		System.out.print(r.data);
	}
	public void inorderNR(Node<T> root){
		Node<T> r = root;
		Stack<Node<T>> s = new Stack<Node<T>>();
		while(r!=null){
			s.push(r);
			r=r.left;
		}
		while(s.size()!=0){
			r = s.pop();
			System.out.print(r.data);
			if(r.right!=null){
				r = r.right;
				while(r!=null){
					s.push(r);
					r=r.left;
				}
			}
		}
	}
	
	public void levelOrder(Node<T> r){
		Queue<Node<T>> queue = new LinkedList<Node<T>>();
		queue.offer(r);
		while(queue.size()!=0){
			Node<T> tmp = queue.poll();
			if(tmp!=null){
				System.out.print(tmp.data);
				queue.offer(tmp.left);
				queue.offer(tmp.right);
			}
		}
	}
	
	public void insert(T data){
		if(root == null){
			root = new Node<T>(data);
		}
		else{
			if(data.compareTo(root.data)<=0){
				if(root.left == null)
					root.left = new Node<T>(data);
				else
					add(data,root.left);
			}
			else{
				if(root.right == null)
					root.right = new Node<T>(data);
				else
					add(data,root.right);
			}
		}
	}
	public void add(T data, Node<T> r){
		if(data.compareTo(r.data)<=0){
			if(r.left == null)
				r.left = new Node<T>(data);
			else
				add(data,r.left);
		}
		else{
			if(r.right == null)
				r.right = new Node<T>(data);
			else
				add(data,r.right);
		}
	}
	
	public int findDepthR(Node<T> r, int level){
		if(r==null){
			return level;
		}
		return Math.max(findDepthR(r.left,level+1), findDepthR(r.right,level+1));
	}
	
	public void mirrorR(Node<T> r){
		if(r==null)
			return;
		Node<T> tmp = r.left;
		r.left = r.right;
		r.right = tmp;
		mirrorR(r.left);
		mirrorR(r.right);
	}
	
	public void mirrorNR(Node<T> r){
		Stack<Node<T>> stack = new Stack<Node<T>>();
		stack.push(r);
		Node<T> tmp;
		while(!stack.isEmpty()){
			tmp = stack.pop();
			if(tmp!=null){
				Node<T> swap = tmp.left;
				tmp.left = tmp.right;
				tmp.right = swap;
				stack.push(tmp.left);
				stack.push(tmp.right);
			}
		}
	}

	// implementation of remove have to take care of the children of the node, look at later.
//	public void remove(T data, Node<T> r, Node<T> prev){
//		if(r.data.equals(data)){
//			if(r.left == null && r.right == null){
//				r = null;
//			}
//			if(r.left == null && r.right != null){
//				prev
//			}
//		}
//	}

	public static void main(String[] argv){
		BST<String> o = new BST<String>();
		o.insert("F");
		o.insert("B");
		o.insert("G");
		o.insert("A");
		o.insert("D");
		o.insert("I");
		o.insert("C");
		o.insert("E");
		o.insert("H");
		o.levelOrder(o.root);
		System.out.println();
		o.mirrorNR(o.root);
		o.levelOrder(o.root);
		System.out.println();
		o.mirrorR(o.root);
		o.levelOrder(o.root);
		System.out.println();
	}
	
}
